\documentclass[a4paper,11pt]{scrartcl}
\usepackage[ngerman]{babel} 
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\usepackage{dsfont}
\usepackage{geometry}
\usepackage{graphicx}

\geometry{a4paper,left=18mm,right=18mm, top=18mm, bottom=2cm} 
\setlength{\columnsep}{120pt}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{Universeller Öffnungscode und 17x17}
\rhead{Martin Thoma}


\setcounter{secnumdepth}{2}
\setcounter{tocdepth}{2}

\begin{document}
 \title{17x17 Problem}
 \author{Martin Thoma}

 \setcounter{section}{1}
 \section*{Das 17x17 Problem}
 Das 17x17 Problem bezieht sich auf die Färbung mit vier Farben.
 \subsection{Zahlen}
   \begin{itemize}
     \item Anzahl der möglichen Färbungen: $4^{(17^2)} = 4^{289} \approx 9,89 \cdot 10^{173}$
     \item Anzahl der 4er Permutationen: $\binom{17}{4} = 2380$
     \item Anzahl der 5er Permutationen: $\binom{17}{5} = 6188$
     \item Anzahl aller Kombinationsmöglichkeiten: $\binom{2380+6188}{17} = \binom{8568}{17} \approx 2,00 \cdot 10^{52}$
     \item Wenn es eine Lösung gibt, gibt es mindestens: $17! \cdot 17! \approx {3,56 \cdot 10^{14}}^2 \approx 1,27 \cdot 10^{29}$. 
           Von diesen Lösungen können allerdings einige identisch sein.
   \end{itemize}

 \subsection{Lösungsfindung}
 \subsubsection{Bruteforce}
    \begin{tabular}[c]{|c|r|r|r|r|r|r|r|r|l|}
    m/n & 1 & 2  & 3  & 4   & 5   & 6   & 7    & 8    & Bemerkung\\
    1   & - & 3  & 7  & 15  & 31  & 63  & 127  & 255  & $2^n - 1$ (es wird nur eine Farbe benötigt)\\
    2   & 3 & 14 & 44 & 128 & 352 & 928 & 2368 & 5888 & $\sum_{k=0}^{n+2} \binom{n+2}{k} \cdot \lfloor k/2 \rfloor^2$ - ACHTUNG! 3 passt nicht in A007466 \\
    \end{tabular}
 \subsubsection{4x4 mit 2 Farben}
\begin{verbatim}
[0, 0, 0, 1]
[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 0, 0]
\end{verbatim}

 \subsubsection{5x4 mit 2 Farben}
\begin{verbatim}
['0', '0', '1', '1']
['0', '1', '0', '1']
['0', '1', '1', '0']
['1', '0', '0', '1']
['1', '0', '1', '0']
\end{verbatim}

 \subsubsection{6x4 mit 2 Farben}
\begin{verbatim}
['0', '0', '1', '1']
['0', '1', '0', '1']
['0', '1', '1', '0']
['1', '0', '0', '1']
['1', '0', '1', '0']
['1', '1', '0', '0']
\end{verbatim}

 \subsubsection{6x6 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 2]
[0, 1, 2, 2, 2, 1]
[1, 2, 0, 1, 2, 1]
[1, 2, 0, 2, 1, 2]
[2, 2, 2, 0, 1, 1]
\end{verbatim}

 \subsubsection{7x7 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 2, 2, 2]
[0, 1, 2, 2, 1, 1, 2]
[1, 2, 1, 2, 1, 2, 0]
[1, 2, 2, 1, 2, 1, 0]
[2, 0, 1, 2, 2, 1, 1]
[2, 0, 2, 1, 1, 2, 1]
\end{verbatim}

 \subsubsection{8x8 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 1, 1, 1, 2, 2]
[0, 1, 1, 2, 0, 0, 0, 0]
[0, 1, 2, 2, 1, 2, 1, 1]
[1, 0, 1, 0, 2, 1, 0, 2]
[1, 0, 2, 1, 2, 0, 2, 1]
[2, 2, 2, 0, 0, 1, 1, 2]
[1, 2, 0, 0, 1, 2, 2, 0]
[2, 0, 1, 1, 2, 2, 1, 0]
\end{verbatim}

 \subsubsection{10x10 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 0, 1, 1, 2, 2, 1, 2]
[0, 1, 1, 2, 0, 0, 0, 2, 2, 1]
[2, 0, 1, 2, 0, 1, 1, 0, 0, 2]
[2, 1, 0, 1, 1, 0, 2, 0, 2, 0]
[0, 1, 2, 2, 2, 1, 2, 1, 0, 0]
[2, 0, 1, 1, 2, 2, 0, 1, 1, 0]
[1, 2, 0, 1, 2, 1, 0, 2, 0, 1]
[1, 1, 2, 0, 0, 2, 1, 2, 1, 0]
[2, 2, 2, 0, 1, 0, 1, 1, 0, 1]
[1, 2, 1, 0, 1, 2, 0, 0, 2, 2]
\end{verbatim}
Source: http://www.cs.umd.edu/~gasarch/papers/gridtalk.pdf

 \subsubsection{11x11 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3]
[0, 1, 1, 1, 2, 2, 3, 0, 0, 0, 0]
[0, 1, 2, 2, 2, 3, 3, 1, 1, 1, 1]
[0, 1, 3, 0, 0, 0, 0, 2, 3, 2, 2]
[0, 1, 3, 2, 3, 1, 1, 3, 2, 2, 3]
[0, 2, 1, 2, 3, 2, 1, 1, 3, 3, 2]
[0, 2, 1, 3, 1, 3, 2, 3, 3, 2, 1]
[0, 3, 3, 3, 2, 1, 3, 1, 2, 3, 2]
[1, 0, 2, 0, 1, 2, 2, 0, 3, 1, 3]
[2, 2, 0, 3, 1, 0, 1, 2, 1, 0, 3]
[1, 3, 0, 1, 0, 2, 1, 3, 0, 2, 1]
\end{verbatim}

 \subsubsection{12x12 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]
[0, 1, 1, 1, 2, 2, 3, 0, 0, 0, 1, 0]
[0, 1, 2, 2, 2, 3, 3, 1, 1, 1, 2, 1]
[0, 1, 3, 0, 0, 0, 0, 2, 3, 2, 2, 2]
[0, 1, 3, 2, 3, 1, 1, 3, 2, 3, 0, 2]
[0, 2, 1, 3, 1, 3, 1, 3, 2, 1, 2, 3]
[0, 3, 2, 3, 1, 2, 2, 1, 3, 3, 1, 2]
[1, 0, 1, 3, 3, 1, 3, 1, 2, 2, 3, 0]
[1, 2, 0, 0, 2, 3, 1, 2, 0, 3, 1, 1]
[1, 3, 3, 1, 0, 2, 3, 0, 2, 1, 0, 3]
[3, 1, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3]
[3, 3, 0, 2, 1, 0, 2, 3, 1, 2, 3, 0]
\end{verbatim}

 \subsubsection{13x13 mit 3 Farben}
\begin{verbatim}
[0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]
[0, 1, 1, 1, 1, 2, 2, 3, 0, 0, 0, 1, 0]
[0, 1, 2, 2, 2, 2, 3, 3, 1, 1, 1, 2, 1]
[0, 1, 3, 2, 0, 0, 0, 0, 2, 3, 2, 3, 2]
[0, 1, 3, 3, 2, 3, 2, 1, 3, 2, 2, 0, 3]
[0, 2, 1, 3, 3, 1, 3, 1, 1, 3, 3, 2, 2]
[1, 0, 2, 1, 3, 0, 2, 1, 3, 0, 1, 0, 2]
[1, 3, 3, 0, 3, 2, 1, 0, 1, 2, 0, 1, 2]
[3, 2, 0, 2, 1, 3, 0, 1, 0, 2, 3, 0, 1]
[3, 3, 0, 1, 2, 0, 3, 2, 3, 1, 0, 3, 2]
[2, 3, 0, 1, 0, 1, 2, 3, 2, 0, 3, 2, 1]
[2, 2, 1, 0, 0, 2, 1, 3, 3, 1, 2, 0, 0]
[3, 2, 2, 0, 3, 1, 0, 3, 2, 0, 1, 1, 3]
\end{verbatim}

\end{document}
